This invention generally pertains to managing the allocation and reclamation of computer resources, including computer memory, which is generally know as “garbage collection.” In particular, the invention is related to garbage collection in distributed computing systems. Therefore, some background regarding distributed computing systems and techniques is first provided, followed by a description of the background for garbage collection.
Distributed Computing Systems
A distributed system is a collection of autonomous computing entities, hardware or software, connected by a communication medium. While often the computing entities are geographically dispersed, in some instances they might be separate processors in a multi-processor computer or even separate software routines executing in logically isolated memory space on the same computer. A computing entity need not be a traditional computer, but more generally can be any computing device, ranging from a large mainframe to a refrigerator or a cell phone. A distributed application is an application that executes on a distributed system and one in which parts of the application execute on distinct autonomous computing entities.
Whenever a distinct component of a distributed application requests something (e.g., a data value, a computation) of another component, the former is called a client and the latter is called a service. It is worth noting that the terms service and client are not exclusionary in that an item can be both a client and a service. For example, a routine that calculates the time between two events may be a client and of a clock service; if the clock service then calls a routine that converts to Daylight Savings Time, the clock becomes a client and the Daylight Savings Time converter is its service.
Mobile code generally refers to a computer program that can be written on one platform and executed on numerous others, irrespective of differences in hardware, operating system, File system, and many other details of the execution environment. In addition to independence from the physical characteristics of the execution environment, a mobile program may move from one computer to another in the middle of its execution.
Mobile code may be pre-compiled, or compiled when it arrives at the execution platform In the first case, numerous versions of the program must be written and compiled, then matched across run-time environments; this is mobile code in the letter, but not the spirit, of the definition. In addition, the same pre-compiled program cannot move from one platform to a different one during its execution. In the second, the program text may be distributed along with configuration scripts describing what to do in each execution environment. This distributes and delays the specificity of the pre-compiled option. The more interesting, and far more common approach exploits a standard virtual machine, which finesses all the issues of platform heterogeneity. The virtual machine is a program that itself mitigates the machine dependencies and idiosyncrasies, taking the raw program text and compiling it to a binary executable.
FIG. 1 shows a typical distributed application of the existing art. There are two clients 2, 4 and four services 10, 12, 14, 16 that the clients 2, 4 might need. Each service has a service proxy 10a, 12a, 14a, 16a which is a module of mobile code that can be used by clients to invoke that service. A service proxy 10a, 12a, 14a, 16a contains the code needed by a client 2, 4 to interact with a service. For instance if a service is a digital camera on a robotic arm, the interfaces might include Initialize( ), Zoom( ), Rotate( ) and Get_Picture( ). The service proxy 10a, 12a, 14a, 16a may also provide the expected return values for the service, which might include error codes as well.
In addition to clients 2, 4 and services 10, 12, 14, 16 distributed applications need some mechanism for clients to find services. Often such knowledge is assumed a priori, but many distributed applications use a look-up service. The look-up service 20 is a service with which the other services are registered or advertised to be available for use by clients. In a simple system, where there is no attempt to coordinate replicas of services, each new service registers with the look-up service 20 (in the case of replicas, the onus falls on the client to resolve conflicts and ambiguity). When a services 10, 12, 14, 16 registers, it provides information telling clients 2, 4 how to find it. Commonly, this is a physical location such as an IP address and port number, but in the most modern systems this can be as powerful as giving the look-up service 20 a service proxy 10a, 12a, 14a, 16a, which is mobile code that clients 2, 4 execute and use to invoke the services 10, 12, 14, 16. In this way, the service proxy 10a, 12a, 14a, 16a contains not only location information but instructions for how to use the services 10, 12, 14, 16. While just as necessary for the client 2, 4 as location information, this has generally been assumed as a priori knowledge. When a client 2, 4 wishes to work with a service 10, 12, 14, 16 it locates it through the look-up service 20, downloads the service proxy 10a, 12a, 14a, 16a for that service 10, 12, 14, 16 from the look-up service 20, then uses the service proxy 10a, 12a, 14a, 16a to invoke the service 10, 12, 14, 16. The look-up service 20 may also have attributes of the services 10, 12, 14, 16, such as whether it is a grouped service, what type of group it is, what its cost to use is, how accurate it is, how reliable it is, or how long it takes to execute. In such cases the clients 2, 4 can use the attributes to decide which of a number of services 10, 12, 14, 16 it wishes to use.
Each of the foregoing has access to a communication network 22 so that it is capable of communicating with at least some of the other members in the distributed computing application. The communication network 22 may be wireless, a local area network, an internal computer bus, a wide area network such as the Internet, a corporate intranet or extranet, a virtual private network, any other communication medium or any combination of the foregoing.
In the prior art example shown in FIG. 1, one client 2 is a roadway traffic monitoring program that notifies a user when and where traffic has occurred and the other client 4 is an automated toll collection program. The services are a clock 10, a road sensor 12 that monitors traffic flow on a highway, a toll booth sensor 14 that detects an ID device in each car that passes through the toll, and a credit card charge program 16. When each service 10, 12, 14, 16 becomes available to the application it registers with the look-up service 20 and provides the look-up service with its service proxy 10a, 12a, 14a, 16a. 
When the traffic monitoring client 2 begins, it queries the look-up service to see if a clock is available and what sensors are available. The look-up service 20 responds by providing the client 2 with the clock proxy 10a, the road sensor proxy 12a and the toll booth sensor proxy 14a. The traffic monitoring client 2 uses the service proxies 10a, 12a, 14a to invoke the clock 10 and the sensors 12, 14, and then to monitor traffic at various times of the day.
Similarly when the toll collector client 4 begins, it queries the look-up service 20 to see if a toll booth sensor 14 and a credit card charge service 16 are available. The look-up service 20 responds by providing this client 4 with the toll booth sensor proxy 14a and the credit card charge proxy 16a. The toll collector client 4 uses the service proxies 14a, 16a, to invoke the toll booth sensor 14 and the credit card charge program 16, and then to identify cars that pass through the toll booth and charge their credit cards for the toll.
A known technique in the existing art is leasing. A lease is an important concept throughout distributed computing, generally used between a client and service as a way for the service to indicate its availability to the client for a length of time. At the end of the lease, if the lease is not renewed, there is no guarantee of availability. In a simple example, a service may register with a look-up service and be granted a lease for five minutes. This means that the lookup service will make itself available to the service (i.e., list it) for five minutes. If a camera grants a lease to a client for two minutes, then that client will be able to position, zoom, and take pictures for two minutes. There are a wide variety of ways to handle lease negotiation, renewal and termination which are well known to those skilled in the art of distributed computing and all such methods are meant to be incorporated within the scope of the disclosed invention. A detailed explanation of leases can be found in, Jim Waldo, The Jini Specification, 2nd Edition, chapter LE (2001), which is incorporated herein by reference.
One useful aspect of leases is that they can be used for simple failure detection. If the expectation is that a client will continue to request lease renewal from a service, but then does not renew its lease, the service may assume that the client has failed, or is otherwise unavailable This allows the service to more efficiently manage its own resources, by releasing any that were dedicated to expired clients.
This is especially important because components only rarely plan and announce their failure and are not able to predict network outages. It is far more common that failures and outages are unexpected, and that the consequence is an inability to announce anything. In these cases, a client will not renew its lease so that eventually, the granting service will reallocate its resources. The shorter the lease period, the sooner a failure can be detected. The tradeoff is that both client and service spend proportionately more time and resources dealing with leasing.
Jini is one example of a commercially available specification for a distributed object infrastructure (or middleware) for more easily writing, executing and managing object-oriented distributed applications. Jini was developed by Sun Microsystems and is based on the Java programming language; consequently, objects in a Jini system are mobile. Jini is described in Jim Waldo, The Jini Specification, 2nd Edition (2001). The Common Object Request Broker Architecture (CORBA), developed by the Object Management Group, and Distributed Component Object Module (DCOM), developed Microsoft Corporation, are two other commercially available examples that are well known in the prior art. Jini, DCOM, CORBA and a number of other distributed computing specifications are described by Benchiao Jai et al., Effortless Software Interoperability with Jini Connection Technology, Bell Labs Technical Journal, April-June 2000, pp. 88-101, which is hereby incorporated by reference.
Garbage Collection
In modern computer systems, regardless of whether they are distributed or centralized, resources are allocated to an object when it is instantiated, and in some cases later during the object's existence if the object requests additional resources. Typically the resource is computer memory, but it may also include other needed system resources such as disk space, processing power or communication bandwidth. In many instances, once the resources are allocated to an object no other object can use this resource until the first object releases (or does not renew) the resource, regardless of whether or not the first object is actually using the resource. For example, if a particular block of memory is allocated for an object to execute in, no other object can use this memory space. In other circumstances, multiple objects may use a single resource, but there may be a limit to the amount of that resource available. For instance, a communication channel with 20 Mb of bandwidth may guarantee 8 Mb of bandwidth to two different objects, but when a third object requests another 8 Mb, the request should be denied.
In the ideal world, each object would release resources either when it finishes execution or when it will not be needing a particular resource for an extended period of time. Unfortunately, many objects are not “well behaved” and fail to appropriately release resources. Even well behaved programs sometimes crash or hang before they can release their resources. This is why leasing, described above as a failure detection mechanism, can be used as the trigger for garbage collection to begin. This problem is further complicated in distributed applications where the communication channel between an object and a resource may be interrupted, thereby preventing the object from releasing the resource, or causing the resource to believe the object has crashed.
Resource allocation is the process by which portions of resources are reserved for objects in a computer system to use. Garbage collection is the process by which these reserved resources are “freed up”, or deallocated so that other objects can use them.
The problem of unused resources not being freed is familiar even to many casual personal computer users. Many times a personal computer will indicate that it has low or insufficient memory, even though the user has no software other than the operating system running. The common way to solve this problem is to reboot the computer, which frees all resources from all objects and restarts the computer from a pure state. This (not very optimal) way of performing garbage collection penalizes all objects rather than just those responsible for hogging memory.
One problem inherent is garbage collection is that a resource may be released when the object is still expecting it to be there. At best this will cause the object to have to reacquire the needed resource, but it may also cause a less robust object to report an error or to crash. For example, a straightforward garbage collector may be programmed to free any resource that has not been used for more than sixty seconds. Now consider that an object may not be able to call a resource for longer than that time because its communication link is down, but that the object is still invoking and queuing calls to the resource. When the communication link is re-established, the object will send the calls to a resource that is no longer available to it, causing the object to fail, or perhaps even causing conflicts and incorrect behavior for the resource. On the other hand, if the garbage collector waits for five minute of inactivity to free up the resource, that resource may go underutilized causing other objects to delay or block because they cannot access that resource. Thus tension exists between the “aggressiveness” of the garbage collector, and the goal of ensuring that objects have the resources they expect. Garbage collection for a scarce resource may be more aggressive, while it would be less aggressive where reliability is of greater concern. Different garbage collection algorithms are optimized for different types of applications, and may be further tuned to make them more or less aggressive. For instance, in the simple algorithm described above, the lapse time could be varied to make the garbage collector more or less aggressive.
One means of garbage collection is reference counting. Each object has a reference, or a pointer, to each resource that it uses. The garbage collection routine can monitor the number of references to each resource and free up the resource when there are no longer any references. This method tends to work best in localized (non-distributed) applications where a single operating system can monitor the references. It is difficult for a remote routine to monitor references on another computer accurately and in a timely manner; specifically, a communication lapse may cause the garbage collector to believe the reference is gone.
Leasing, a technique describe above, is an effective method of garbage collection. When the lease ends the resource is released, unless the lease has been renewed. Such a use of leasing is described in U.S. Pat. No. 5,832,529 to Wollrath et al., entitled “Methods, Apparatus, and Product for Distributed Garbage Collection.”
Another known technique for garbage collection is for the garbage collector or a resource to “ping” the object (or objects) using a resource at fixed intervals. A response to the ping from the object indicates that the object is operating—it has not crashed or hung and the network connection to it is viable. One problem with this method is the amount of non-useful communication injected in the network; another problem is that it requires reliable two-way communication in order to maintain the object's liveness.
Another known technique for garbage collection is last reference time stamp. In this technique, a period of time is allocated to each object that uses a resource. If the object does not use that resource (e.g., no calls are received by the resource from that object) within the time period, the resource is released from that object.
One problem with the current forms of garbage collection is that they use a constant algorithm. However at different times, or under different ambient conditions, or even (in the case of shared resources) for different requesting objects, different types of algorithms may be appropriate. During periods of high contention for a resource, an aggressive algorithm might be desirable. When the system is having network communication problems, a less aggressive algorithm might be desirable. When a resource is highly shared (i.e., has many concurrent users) leasing may be preferable, whereas when it is lightly shared reference counting, while globally less efficient, would be acceptable with the accompanying benefits of improved accuracy. Current garbage collection systems do not allow for such variation.
Another restriction is that garbage collection is currently conducted by a specific garbage collection system which examines each resource according to the previously described algorithms, and decides whether or not to recall them. Resources do not garbage collect themselves when they detect they are no longer needed.
It is therefore an object of the present invention to provide a method of garbage collection that can dynamically switch between different garbage collection algorithms.
It is a further object of the present invention to provide a method of garbage collection in which the parameters of a given algorithm can be dynamically modified.
It is a further object of the present invention to provide a method of garbage collection wherein the garbage collection algorithms are written as separate mobile code objects.
It is a further object of the present invention to provide a method of garbage collection wherein resources can garbage collect themselves according to various and numerous criteria.